home *** CD-ROM | disk | FTP | other *** search
/ Java Developer's Companion / Java Developer's Companion.iso / documentation / tutorial / java / threads / example / QSortAlgorithm.java < prev    next >
Encoding:
Text File  |  1997-07-13  |  2.4 KB  |  79 lines
  1. /*
  2.  * Copyright (c) 1995-1997 Sun Microsystems, Inc. All Rights Reserved.
  3.  *
  4.  * Permission to use, copy, modify, and distribute this software
  5.  * and its documentation for NON-COMMERCIAL purposes and without
  6.  * fee is hereby granted provided that this copyright notice
  7.  * appears in all copies. Please refer to the file "copyright.html"
  8.  * for further important copyright and licensing information.
  9.  *
  10.  * SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF
  11.  * THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
  12.  * TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
  13.  * PARTICULAR PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR
  14.  * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
  15.  * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
  16.  */
  17. /*
  18.  * @(#)QSortAlgorithm.java    1.6f 95/01/31 James Gosling
  19.  *
  20.  * Copyright (c) 1994 Sun Microsystems, Inc. All Rights Reserved.
  21.  *
  22.  * Permission to use, copy, modify, and distribute this software
  23.  * and its documentation for NON-COMMERCIAL purposes and without
  24.  * fee is hereby granted provided that this copyright notice
  25.  * appears in all copies. Please refer to the file "copyright.html"
  26.  * for further important copyright and licensing information.
  27.  *
  28.  * SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF
  29.  * THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
  30.  * TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
  31.  * PARTICULAR PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR
  32.  * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
  33.  * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
  34.  */
  35.  
  36. /**
  37.  * A quick sort demonstration algorithm
  38.  * SortAlgorithm.java, Thu Oct 27 10:32:35 1994
  39.  *
  40.  * @author James Gosling
  41.  * @version     1.6f, 31 Jan 1995
  42.  */
  43. class QSortAlgorithm extends SortAlgorithm {
  44.     void sort(int[] a, int lo0, int hi0) throws Exception {
  45.     int lo = lo0;
  46.     int hi = hi0;
  47.     pause(lo, hi);
  48.     if (lo >= hi) {
  49.         return;
  50.     }
  51.     int mid = a[(lo + hi) / 2];
  52.     while (lo < hi) {
  53.         while (lo<hi && a[lo] < mid) {
  54.         lo++;
  55.         }
  56.         while (lo<hi && a[hi] > mid) {
  57.         hi--;
  58.         }
  59.         if (lo < hi) {
  60.         int T = a[lo];
  61.         a[lo] = a[hi];
  62.         a[hi] = T;
  63.         pause();
  64.         }
  65.     }
  66.     if (hi < lo) {
  67.         int T = hi;
  68.         hi = lo;
  69.         lo = T;
  70.     }
  71.     sort(a, lo0, lo);
  72.     sort(a, lo == lo0 ? lo+1 : lo, hi0);
  73.     }
  74.  
  75.     void sort(int[] a) throws Exception {
  76.     sort(a, 0, a.length-1);
  77.     }
  78. }
  79.